package com.le.medium.class5;

/**
 * 给定一个数组arr，如果通过调整可以做到arr中任意两个相邻的数字相乘是4的倍数，返回true；如果不能返回false
 */
public class Problem03_NearMultiple4Times {
    // 2的倍数个数为0 ： 奇4奇4奇4奇4奇4奇4奇4奇4 最好的排列 4的个数加一 大于等于奇数的个数
    // 2的个数大于0：222...4 奇4奇4奇4 ---> 偶数个数大于等于奇数个数 成立
    public static boolean nearMultiple4Times(int[] arr){
        int four = 0; // 4的倍数的个数
        int two = 0; // 2的倍数的个数
        int odd = 0; // 奇数的个数
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & 1) != 0){
                odd++;
            }else {
                if (arr[i] % 4 == 0){
                    four++;
                }else {
                    two++;
                }
            }
        }
        return two == 0 ? (four + 1) >= odd : two >= odd;

    }
}
